class Solution
{
public:
    int rob(vector<int> &nums)
    {
        int n = nums.size();
        // dp[0][i]表示不抢第i家时的最大收益，dp[1][...]表示抢
        vector<vector<int>> rubDp{vector<int>(n), vector<int>(n)};
        rubDp[0][n - 1] = 0;
        rubDp[1][n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; --i)
        {
            rubDp[0][i] = max(rubDp[0][i + 1], rubDp[1][i + 1]);
            rubDp[1][i] = nums[i] + rubDp[0][i + 1];
        }
        return max(rubDp[0][0], rubDp[1][0]);
    }
};